Wireless communication among electronic devices has been increasing as the benefits and conveniences of wireless communication become more preferred. A wireless communication system or wireless network is often described as containing nodes (or more precisely, circuitry associated with the concept of a node) and a wireless medium (WM) over which the nodes' circuitry communicate to convey information. Where some action or activity is described as happening at (or being done at) a node, it should be understood that the electronic device and/or network interface that is at (or simply is) the node is the circuitry that is performing the action or activity. For example, sending data from node A to node B means transmitting a signal from circuitry associated with node A and receiving that signal (or more precisely, the transmitted signal modified by the medium) using circuitry associated with node B.
The information conveyed between nodes can be digital data and digitized analog signals, or other forms of information, but communication system design often assumes that digital data is being conveyed and higher network layers interpret the data appropriately. For purposes herein, it is assumed that data exists at one node, is provided to lower network layers, is conveyed to another node over a WM, is received by another node correctly or incorrectly and then is conveyed to upper network layers at the receiver. In one model, two networked devices run applications that pass data between themselves by having the sending device's application convey data to an application layer of a network stack, which conveys data to lower levels, ultimately to a medium access control (MAC) layer and a physical network (PHY) layer, and the process is inverted at the recipient.
To set up a wireless network, all that is needed is a plurality of electronic “node” devices capable of transmitting and receiving data in a manner understood by the two (or more) nodes involved in a conversation, with the node devices appropriately placed such that they can communicate in the medium that exists between the devices. The medium could be some type of dielectric material, but more commonly, the medium is the air space and objects (walls, chairs, books, glass. etc.) that are between devices or are positioned such that they have an effect on the signals transmitted between devices. Presumably, the node devices are assigned unique identifiers to distinguish transmissions, but this might not always be necessary. Examples of such unique identifiers are MAC addresses and IP addresses.
As the existence of various wireless media and their properties are known and are not the focus of this disclosure, the medium is often just shown in the attached figures as a cloud. Thus, it should be understood that supplier of a set of two or more powered devices that can communicate supplies a wireless network; the wireless medium is presumed.
In some networks, one of the node's device is the controller for the network and the other devices are followers. For example, in an 802.11x network operating in infrastructure mode, one of the nodes is an “access point” (AP) and the other nodes are stations (“STAs”). In some networks, such as personal area network or “PAN”, the controller is a computing device and the other nodes are peripherals associated with that computing device.
In general, a wireless connection between two or more devices requires that each device include wireless network circuitry for conveying signals over the medium and receiving signals over the medium, as well as processing/communication circuitry to receive, process and/or convey data and/or signals to that wireless network circuitry. The processing/communication circuitry could be implemented with actual circuits, software instructions executable by a processor, or some combination thereof. In some variations, the wireless network circuitry and processing/communication circuitry are integrated (such as with some PDAs, wireless mice, etc.) or are separate elements (such as a laptop as the processing/communication circuitry and a network PCMCIA card as the wireless network circuitry).
For ease of understanding this disclosure, where it is important to make the distinction between devices, a device that exists to provide wireless connectivity is referred to as a “network interface”, “network interface device”, “wireless network interface device” or the like, while the device for which the wireless connectivity is being provided is referred to as a “computing device” or an “electronic device” notwithstanding the fact that some such devices do more than just compute or might not be thought of as devices that do actual computing and further notwithstanding the fact that some network interface devices themselves have electronics and do computing. Some electronic devices compute and communicate via an attached network interface device while other electronic devices might have their network interface devices integrated in a non-detachable form. Where an electronic device is coupled to a wireless network interface to a wireless network, it is said that the device is a node in the network and thus that device is a “node device”.
A communication system provides for transfers of data and messages between devices, such as device-to-device transfers and broadcast transfers. Where the communication system is used by a number of electronic devices wherein the number and/or set of electronic devices that are coupled to the communications system at any given time is not known to each of the electronic devices, such electronic devices may need to have a mechanism for discovering which electronic devices are presently coupled to the communications system or at least whether a particular electronic device is presently coupled to the communications system.
An “initiating device” is an electronic device coupled to the communications system that desires to exchange information, data and/or signals with another electronic device, herein referred to as a “destination device”. As part of the exchange process, the two devices first form a “connection”. A connection might be set up using operations such as device detection, negotiation and/or exchange of specific communication parameters and/or security information, and initiation of a synchronization procedure.
The communication system might use “channels” to convey signals, wherein signals flow over a plurality of channels and are assumed to be separate signals, even though they might be combined in transit. For example, a communication system might include a signal transmission medium that is divided into a plurality of channels by time division, frequency division, division by protocol, encoding scheme and/or data rate, etc., or a combination of some or all of the above and other channel definition criteria.
Device detection by an initiating device typically involves a scanning operation to locate the channel of the destination device. As an example, if the initiating device does not know which of a plurality of time slots is associated with the destination device such that the destination device can be “found” in that associated time slot, the initiating device might scan over a number of time slots looking for the destination device (i.e., attempting to detect its presence so that a connection could be established). The destination device may, for example, be unavailable during certain periods of time because it has powered down parts or all of its circuits, or because it is communicating with one or more electronic devices other than the initiating device. Such other devices may or may not be part of the same communication system as the initiating device. As another example, detection in frequency may be necessary if the frequency of operation of the destination device is not a priori known by the initiating device.
In many applications, it is desirable that device detection happens sufficiently fast such that no significant delay is added to the connection process. This may, for example, be important in latency-sensitive applications where noticeable delays degrade the user experience and/or the performance of the network. An example of a latency-sensitive communication system is a communication system over which a personal computer (PC) and a wireless mouse might communicate.
In such a system, a user moves the mouse, the mouse connects with the PC, communicates messages indicating the movement, the PC receives the message and interprets it, and then the PC's applications show the appropriate response to the movement (e.g., moving a cursor, selecting an item). Typically, none of the system components can predict when a user will start to move a mouse that has been sitting motionless, but the user will expect that the application respond in apparently real-time (i.e., without noticeable delay, undesirable delay, or both). For this to occur, the PC and mouse must maintain a constant connection to be ready when the unpredictable mouse movement occurs or must be able to set up a connection quickly when the unpredictable mouse movement does occur. In the former case, considerable power might be expended maintaining the connection during periods of inactivity, which would be wasteful.
In many applications, it is important that device detection be implemented in a power efficient way. This is particularly important when the initiating device and/or destination device are battery operated devices. As an example, when the communication system comprises a cellular phone as a destination device and a cordless headset as an initiating device, device detection should not significantly impact the battery life of either the phone or the headset.
Different scanning mechanisms exist and may be used for device detection. They typically comprise one device, herein referred to as the “probing” device, actively sending packets, herein referred to as “probe request packets”, and one or multiple other devices, herein referred to as the “listening” devices, passively listening for probe request packets from a probing device. Since the probing device might not a priori know which and how many listening devices may be listening at a given moment in time, the probing packet is usually constructed in such a way that it is addressed to all listening devices. As an example, if the communication system is a wireless Local Area Network (WLAN) based on one or more of the 802.11 specifications (such as 802.11a, .11b, .11e, .11g, .11n, etc.; referred to herein as “an 802.11 network” or “an 802.11x network”), then the probe request packet is typically built as a broadcast frame.
When a listening device successfully receives a probe request packet, it may respond with a response packet, herein referred to as “probe response packet”. Since there may be multiple listening devices that may be receiving the same probe request packet, a device that desires to send a probe response packet must follow normal frame transmission rules, including regular medium access procedures, in order to prevent collisions and interference on the medium.
A significant delay, herein referred to as the “probe response time”, may exist between a probe request packet being transmitted and a corresponding probe response packet being received due to delay needed for the listening device to perform its medium access procedures.
In some scan methods, the probe response time can be long and can vary widely depending among other things on the medium occupancy. As an example, in a contention-based communication system, like an 802.11-based Carrier-Sense-Multiple-Access based system with collision-avoidance (CSMA/CA), the probe response time may be increased significantly and may vary because of medium arbitration in the presence of other traffic on the medium.
Long and variable probe response times are undesirable in specific applications, as they can significantly increase the power consumption in the initiating and/or destination device and can degrade the connection time. One reason for this is that variable probe response times require the probing device to have its receiver circuitry powered up for a period longer than is needed for the actual reception, because the probing device does not know when the transmission will occur.
This is especially true when probing devices may be probing for listening devices that may or may not be available on the channel where the probing takes place. Indeed, in order to make sure that no probe response packet is missed, a device that has transmitted a probe request packet should wait and listen for a probe response packet for at least the worst case probe response time, if this time can be defined deterministically. Alternatively, the device should wait and listen for a sufficiently long amount of time after sending a probe request packet to statistically ensure that the chance of missing a probe response packet is acceptably small.
In an 802.11x network, specific medium reservation schemes are sometimes used for regular data communication between two connected devices. In such schemes, a first device reserves the medium for a packet that will be transmitted by a second device that is connected to the first device. Such a medium reservation scheme makes it possible to exchange packets between two connected devices without causing collisions or interference on the medium, while bypassing some or all of the normal frame transmission rules or regular medium access procedures.
A medium reservation scheme as described above may be useful for achieving a more reliable data exchange between two or more devices if not all devices do have a communication path to all other devices that are sharing the same communication channel, if one or more devices does not implement the functionality required to make a correct and fair decision about when to access the medium, if not all devices have access to all the information about other devices to be able to make a correct or fair decision about when to access the medium, or for any combination of the above and other reasons.
A common medium reservation system used to increase the reliability of data exchange in 802.11x networks operating in an “infrastructure mode” is a message exchange comprising a Ready-To-Send (RTS) message from a first device, typically a station (“STA”) that is not an access point (“AP”), and a Clear-To-Send (CTS) message from a second device, typically the AP. Prior to sending a packet, a STA may decide to first send an RTS packet to request a medium reservation for its pending packet. The medium reservation in the RTS packet typically includes the time required for the transmission of the pending packet, a CTS packet, possibly an acknowledgement and one or more turnaround intervals (e.g., three Short Interframe Spaces or “SIFS”). The AP receiving the RTS responds with a CTS packet without incurring the delay that may be introduced when following the regular frame transmission rules and regular medium access procedures. The medium reservation in the CTS packet is typically computed from the medium reservation request in the immediately previous RTS packet by subtracting the time required to send a CTS packet and the appropriate turnaround time (e.g., one SIFS). Upon reception of the CTS packet, the device that initiated the RTS/CTS packet exchange may go ahead and transmit its pending frame without incurring delays that may be introduced by following regular medium access procedures.
Another example of a medium reservation mechanism is the controlled channel access mechanism (or “HCCA”) that may be used for periodic high Quality of Service (QoS) traffic in 802.11(e) based infrastructure networks. In such networks, an AP may set up a Traffic Stream (TS) with a non-AP station (STA), and may periodically communicate with the non-AP STA based on the parameters negotiated/specified for the traffic stream. In that case, the communication between an AP and a non-AP STA comprises a poll frame transmitted by the AP and directed to the non-AP STA followed by a poll response frame transmitted by the non-AP STA and directed to the AP. The poll frame reserves the medium for the subsequent poll response frame, thereby allowing the non-AP STA to bypass the normal transmission rules and respond within a considerably shorter response time.
While the medium reservation schemes like the ones described above have been used successfully to increase the reliability and/or Quality-of-Service performance of regular data communication between two connected devices, such schemes assume that both devices have successfully established a connection prior to adopting the schemes for data communication.
In addition, both schemes are used specifically in the context of 802.11x networks that operate in infrastructure mode, where the device making the medium reservation is an Access Point, and not a regular non-AP STA.
What is needed is an improved connection process that does not require a prior connection and provides acceptably low latency.
In light of the above, improved device detection protocols, methods and apparatus are proposed.